1. Field of the Invention
The present invention relates to logic elements for use with programmable logic devices or other similar devices.
2. Description of the Related Art
Programmable logic devices (“PLDs”) (also sometimes referred to as CPLDs, PALs, PLAs, FPLAs, EPLDs, EEPLDs, LCAs, FPGAs, or by other names), are well-known integrated circuits that provide the advantages of fixed integrated circuits with the flexibility of custom integrated circuits. Such devices are well known in the art and typically provide an “off the shelf” device having at least a portion that can be electrically programmed to meet a user's specific needs. Application specific integrated circuits (“ASICs”) have traditionally been fixed integrated circuits, however, it is possible to provide an ASIC that has a portion or portions that are programmable; thus, it is possible for an integrated circuit device to have qualities of both an ASIC and a PLD. The term PLD as used herein will be considered broad enough to include such devices.
PLDs typically include blocks of logic elements, sometimes referred to as logic array blocks (“LABs”; also referred to by other names, e.g., “configurable logic blocks,” or “CLBs”). Logic elements (“LEs”, also referred to by other names, e.g., “logic cells”) may include a look-up table (LUT) or product term, carry-out chain, register, and other elements.
Logic elements, including look-up table (LUT)-based logic elements, typically include configurable elements holding configuration data that determines the particular function or functions carried out by the logic element. A typical LUT circuit may include configuration RAM bits that hold data (a “1” or “0”). However, other types of configurable elements may be used. Some examples may include static or dynamic random access memory, electrically erasable read-only memory, flash, fuse, and anti-fuse programmable connections. The programming of configuration elements could also be implemented through mask programming during fabrication of the device. While mask programming may have disadvantages relative to some of the field programmable options already listed, it may be useful in certain high volume applications. For purposes herein, the generic term “memory element” will be used to refer to any programmable element that may be configured to determine functions implemented by a PLD.
PLDs are commonly constructed using a lookup table (LUT) as the basic logic element. A typical LUT circuit used as a logic element provides an output signal that is a function of multiple input signals. For example, a K-input lookup table (K-LUT) typically includes 2K programmable memory elements, and a 2K to 1 multiplexer, selecting one of the storage elements under the control of the K select (control) inputs to the multiplexer. These K inputs can be considered to be the control inputs to a K-input logic function which can implement any particular required logic function by setting the contents of the memory elements to the appropriate values.
A typical LUT circuit may be represented as a plurality of memory elements coupled to a “tree” of muxes. A typical LUT mux tree includes a first level comprising a single 2:1 mux providing the LUT output and also includes successive additional levels of muxes, each level including twice as many muxes as the previous level and the number of memory elements being twice as many as the number of 2:1 muxes in a last mux level coupled to the memory elements.
FIG. 1 is an illustrative block diagram of logic circuitry 100 that implements the function f(x0,x1,x2,x3). In this example, the value of the function f depends upon a combination of values of inputs x0, x1, x2, and x3. A LUT of a logic element of a PLD may be programmed to serve as the logic circuitry 100 that implements the function f. A signal timing issue may arise if the value of one of the inputs arrives at, or becomes valid at its logic circuit input, significantly later than the values of the other inputs. The circuit path that delivers such later-arriving input signal value is commonly referred to as a critical path. Critical path delay is an important factor in determining overall delay in producing a value of f based upon values for x0, x1, x2, and x3.
Shannon decomposition is a well known technique for reducing the impact of critical path delay upon the speed of operation of a logic circuit. Shannon decomposition is stated as the mathematical theorem:f(x0,x1, . . . )={overscore (x0)}·f(0,x1, . . . )|x0·f(1,x1, . . . )
For notational brevity, f(0,x1, . . . ) is denoted f{overscore (x0)} and f(1,x1, . . . ) is denoted fx0 and are respectively referred to as the {overscore (x0)} and x0 co-factors off.
FIG. 2 is an illustrative block diagram of a circuit 200 to provide a Shannon decomposition of function f(x0,x2,x2,x3) where value x0 is a critical path signal. A first logic circuitry 202 receives as inputs, 0, x1, x2, and x3, and provides as an output, the value for f{overscore (x0)}. A second logic circuitry 204 receives as inputs, 1, x1, x2 and x3 and provides as an output, the value for fx0. A multiplexer 206 receives f{overscore (x0)} and fx0 as data values; receives x0 as a control input value; and provides f as an output value. Delay in the determination of f due to late arrival of critical path value x0 is reduced by pre-computing a value off assuming x0=0 using first circuitry 202 and by also pre-computing a value of f assuming x0=1 using second circuitry 204. In this example, the delay from a time that x0 is valid until a time that the output off is valid is no more than approximately the delay of the multiplexer.
One or more LUTs of one or more LEs may be programmed to serve as the first and second logic circuitry 202, 204 and multiplexer 206 that implement the Shannon decomposition of the function f in FIG. 2. The Shannon decomposition technique of FIG. 2 is of limited use in LUT-based LEs because a LUT is a tree of multiplexers, and a LUT essentially provides a Shannon decomposition of a single stage of the logic.
FIG. 3 is an illustrative drawing of a logic network 300 that implements a logic circuit using two levels of LUTs. The network 300 includes first and second LUTs 302, 304. In this example, a critical path extends from the path of signal x to the path of signal y to the path of signal z. Each LUT 302, 304 may be a constituent of a different LE in a single PLD, for example. The first LUT 302 includes a first pair of LUTs indicated by block 302-1. Multiplexer 302-2 is the first-level multiplexer of the first multiplexer tree of the first LUT 302. The second LUT 304 includes a second pair of LUTs indicated by block 304-1 and multiplexer 304-2. Multiplexer 304-2 is the first-level multiplexer of the second multiplexer tree of the second LUT 302. The first LUT 302 is connected to receive three first control inputs 310 to LUTs 302-1 and is connected to receive signal x as a control input 312 to first-level multiplexer 302-2. LUTs 302-1 are connected to provide outputs yx0 and y{overscore (x0)} as inputs to the first-level multiplexer 302-2. The first-level multiplexer 302-2 provides a value of signal y as an output. The second LUT 304 is connected to receive three second control inputs 314 to LUTs 304-1 and is connected to receive signal y as a control input 316 to first-level multiplexer 304-2. Multiplexer block 304-1 is connected to provide outputs zy0 and z{overscore (y0)} as inputs to first-level multiplexer 302-2. The first-level multiplexer 304-1 provides a value of signal z as an output on line 318.
Signal y output from first LUT 302 is used as input y0 to second LUT 300. Thus y and y0 refer to the same logic signal. Also, signal x is used as input x0 to first LUT 302 so x and x0 refer to the same logic signal. A signal will generally be referred to without the appended digit when used in the context of an output from a logic element, i.e. y is an output of an LE, but referred to with the appended digit when used as input to another logic element, i.e. y0 is an input to another logic element.
In the network 300 of FIG. 3, the value of y depends upon the value of x, and the value of z depends upon the value of y. Although each of signals y and z are implemented with LUTs that naturally form the Shannon decomposition of critical input signals x0 and y0 respectively, the complete circuit still has significant delay, associated with the propagation of signal x through first-level multiplexer 302-2 and may incur delay associated with the propagation of signal y along path 316.
Thus, there is a need for improved LUT based circuits that can achieve Shannon decomposition. The present invention meets this need.